"""
23ms 3200KB 6/7 一个超时
分析：
输入的节点信息，并不是按链表顺序输入的。这意味着必须将输入信息存起来。
有可能存在“虚假节点”，即该节点并不在实际所求的链表上。
由于题目没有交代若该链表是空链表时如何输出，可以认为链表至少有一个节点。
每凑够K个节点来一轮逆置，但最后若凑不够K个则不逆置！所以要预判数量。
注意输出的地址要凑足5位数，除了-1外。
解题思路：
直接映射哈希法存储节点：由分析1，且有效地址是不超过5位数的非负整数，用长度为100000的数组A[]存储节点。
用顺序表模拟链表：用数组link[]按链表的顺序存储输入所代表的链表，但只存储<address,data>，因为可以用下标遍历而不需要next。（反正都用了哈希存储，空间复杂度不可能＜O(N)了）
在顺序表(link[])中完成逆置：每凑够K个节点来一轮逆置，逆置操作用双指针迭代交换完成，最后不足K个节点跳出。
将link[]模拟的链表打印出来：注意链表长度不一定为N，要以实际记录的长度为准，可以在link[]末端插入地址-1作为哨兵。

"""
# -*- coding: utf-8 -*-  
# 思路：从给定的链首到链末共有数据个数n加1项，id为前n项，next为后n项  
def link(address,head,li):  # 采用递归将链表所用节点依次存入列表  
    if head in address:  
        arrow = address[head]  
        li.append(arrow)  
        return link(address,arrow,li)  
    else:  
        return li  
head,N_all,cell = input().split()  # 读取第一行输入：首项元素id，元素个数N_all，反转间隔cell  
N_all,cell = int(N_all),int(cell)  # 将N与cell转换为整数  
address,data = {},{}  # 初始化两个字典，其中address保存id-next关系，data保存id-data关系  
for i in range(N_all):  # 将输入信息存入address和data中  
    a,b,c = input().split()  
    address[a],data[a] = c,b     
# 调用link()函数将所给信息按链接顺序存入id_plus，有N_all+1个元素，末项为链尾指针，指向未知id或为-1  
id_plus = link(address,head,[head])  # 第三项必须为[head]而不是[]，因为link()函数无法添加第一个id  
id_plus[-1] = '-1'  # 指定链尾指针指向-1  
N_e = len(id_plus) - 1  # id_plus中的元素个数为可链接到的元素，从首项到最后的-1，实际对应的数据个数应减1  
num, rem = N_e // cell, N_e % cell  # 判断要对那些数据进行反转  
if num:  # 可链接到的数据个数不小于反转间隔  
    for i in range(num):  
        id_plus[(i*cell):((i+1)*cell)] = id_plus[(i*cell):((i+1)*cell)][::-1]  # 反转  
for k,v in enumerate(id_plus[:-1]):  # 按规定格式，打印id,data,next  
    s = '{} {} {}'.format(v,data[v],id_plus[k+1])  
    print(s)
